package com.example.question.list.list2;

import com.example.question.list.list1.List;
import com.example.question.list.list1.ListNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Date 2023-07-07
 * @Author Jonathan
 */
public class Code02_138 {
    Integer index = 0;
    Map<Node, Node> copyMap = new HashMap<>();
    Map<Node, Node> randomMap = new HashMap<>();

    public static void main(String[] args) {
        Code02_138 code = new Code02_138();
        int[][] arr = {{7, -1}, {13, 0}, {11, 4}, {10, 2}, {1, 0}};
//        Node randomList = code.createRandomList(arr);
//        System.out.println(randomList);
        ListNode listNode = List.createList(new int[]{1, 2, 3, 4, 5});
        List.printLink(listNode);
        ListNode node = code.copyListNode3(listNode);
        System.out.println("\ncopy List:");
        List.printLink(node);


    }

    /**
     * TODO 再思考一下！！！
     */
    public Node copyRandomList1(Node head) {
        if (head == null) {
            return null;
        }
        Node copyNode = new Node(head.val);
        copyMap.put(head, copyNode);
        randomMap.put(head, head.random);
        copyNode.next = copyRandomList1(head.next);
        copyNode.random = copyMap.get(randomMap.get(head));
        return copyNode;
    }

    public Node copyRandomList2(Node head) {
        Node copyNode = new Node(head.val);
        Node copyHead = copyNode;
        copyMap.put(head, copyHead);
        while (head != null/* && head.next != null*/) {
            copyNode.next = getClonedNode(head.next);
            copyNode.random = getClonedNode(head.random);
            copyNode = copyNode.next;
            head = head.next;
        }
        return copyHead;
    }

    /**
     * 不用map
     */
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Node cur = head;
        // 复制
        while (cur != null) {
            Node next = cur.next;
            Node copyNode = new Node(cur.val);
            cur.next = copyNode;
            copyNode.next = next;
            cur = next;
        }
        cur = head;

        // random 指针
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }

        Node old = head;
        Node copy = head.next;
        Node copyHead = copy;
        // 分离
        while (copy != null) {
            old.next = old.next.next;
            // 当copy.next 为null的时候  就不用设置了
            copy.next = copy.next == null ? null : copy.next.next;
            old = old.next;
            copy = copy.next;
        }
        return copyHead;
    }

    private Node getClonedNode(Node node) {
        if (node == null) {
            return null;
        }
        if (!copyMap.containsKey(node)) {
            copyMap.put(node, new Node(node.val));
        }
        return copyMap.get(node);
    }

    /**
     * 递归复制单链表
     */
    public ListNode copyListNode(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode copyNode = new ListNode(head.val);
        copyNode.next = copyListNode(head.next);
        // 每次返回的都是复制好的头结点
        return copyNode;
    }

    /**
     * 用栈模拟递归
     */
    public ListNode copyListNode2(ListNode head) {
        ListNode cur = head;
        Stack<ListNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 最后一个拿出来单独处理
        ListNode tail = null;
        ListNode copyNode = null;
        while (!stack.isEmpty()) {
            copyNode = new ListNode(stack.pop().val);
            copyNode.next = tail;
            tail = copyNode;
        }
        return copyNode;
    }

    /**
     * 迭代复制
     */
    public ListNode copyListNode3(ListNode head) {
        ListNode copyNode = new ListNode(head.val);
        ListNode copyHead = copyNode;
        while (head.next != null) {
            copyNode.next = new ListNode(head.next.val);
            copyNode = copyNode.next;
            head = head.next;
        }
        return copyHead;
    }


    public Node createRandomList(int[][] array) {
        Node head = new Node(array[0][0]);
        Node cur = head;
        // 创建链表
        for (int i = 1; i < array.length; i++) {
            cur.next = new Node(array[i][0]);
            cur = cur.next;
        }
        // random指针
        cur = head;
        int index = 0;
        while (cur != null) {

            cur.random = getKthNode(head, array[index][1]);
            cur = cur.next;
            index++;
        }
        return head;
    }

    private Node getKthNode(Node head, int k) {
        if (k == -1) {
            return null;
        }
        int index = 0;
        while (index < k) {
            head = head.next;
            index++;
        }
        return head;
    }


    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }

//        @Override
//        public String toString() {
//            return "Node{" + "val=" + val + ", next=" + next + ", random=" + random + '}';
//        }
    }
}
